// 单调队列
// https://www.luogu.com.cn/problem/P1886
int n, m;
int a[maxn];

class Monotonic_queue {
  private:
    int l, r, m;
    int qe[maxn]; // for index

  public:
    Monotonic_queue() { clear(); }
    void clear() { l = 0, r = 0; }
    void set_width(int w) { m = w; }
    void push_inc(int i) { // keep inc
        while (l < r && a[qe[r - 1]] > a[i])
            --r;
        while (l < r && i - qe[l] > m - 1)
            ++l;
        qe[r++] = i;
    }
    void push_dec(int i) { // keep dec
        while (l < r && a[qe[r - 1]] < a[i])
            --r;
        while (l < r && i - qe[l] > m - 1)
            ++l;
        qe[r++] = i;
    }
    int front() { return a[qe[l]]; }
} qe;
